package _0_语法._4_循环._2_双循环;

import java.util.Scanner;

public class _8_求最大公约数_1 {

    public static void main(String[] args) {
        int num1;
        int num2;
        int count;                      // 循环次数
        int commonDivisor = 0;          // 公约数
        int greatestCommonDivisor = 1;  // 最大公约数

        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入第一个数：");
        num1 = scanner.nextInt();
        System.out.println("请输入第二个数：");
        num2 = scanner.nextInt();

        // 数大的作为循环次数
        if(num1 > num2) {
            count = num1;
        }
        else {
            count = num2;
        }

        System.out.print(num1 + "," + num2 + "的最大公约数：");

        // 使用短除法，遍历两个数
        for (int i = 2; i < count; i++) {

            // 如果公约数大于商则退出循环，减少循环次数
            if(commonDivisor > num1 / i  || commonDivisor > num2 / i ) {
                break;
            }
            // 同时满足的公约数
            while(num1 % i == 0 && num2 % i == 0) {
                commonDivisor = i;
                // 除以公约数
                num1 = num1 / commonDivisor;
                num2 = num2 / commonDivisor;
                // 累乘求最大公约数
                greatestCommonDivisor = commonDivisor * greatestCommonDivisor;
                System.out.print(commonDivisor + " ");
            }
//            System.out.println("i = " + i); // 测试执行次数
        }
        System.out.println(greatestCommonDivisor);
    }
}
